package com.leetcode.贪心;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 
 * 其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
 * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，
 *  且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
 * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
 * @author LZF
 *
 */
public class L452用最少数量的箭引爆气球 {
	public static void main(String[] args) {
		
	}
	/**
	 * 贪心：
	 * 局部最优：只要区间之前有重叠，就用一直箭将所有重叠区间射掉
	 * 全局最优：把所有区间射掉所用的弓箭最少
	 * 
	 * 要算出所有重叠区间，需要让区间进行排序，可以按开始坐标排序，也可以按结束坐标排序
	 * 前者得从前往后遍历，后者得从后往前遍历
	 * 这里用前者。
	 * 
	 * 排序之后，当前区间i的开始坐标小于前一个区间的结束坐标，则可以合并points[i][0] < points[i - 1][1]
	 * 取开始坐标的较大者做新区间的开始坐标，取结束坐标的较小者做新区间的结束坐标，然后新区间替代区间i
	 * 也就是说区间i变成了两个区间合并的结果，因为后面的区间i+1要跟区间i进行判断
	 * 
	 * 如果不能合并，则到区间i为止，则前面的区间需要一只箭。
	 */
	public static int findMinArrowShots(int[][] points) {
		if(points.length == 0) return 0;
		//对points进行排序，按开始坐标排序
		Arrays.sort(points,(o1,o2) -> Integer.compare(o1[0],o2[0]));
		int result = 0;//一开始要射出的箭为0
		for(int i = 1;i < points.length;i++) {
			if(points[i][0] < points[i - 1][1]) {
//				points[i][0] = Math.max(points[i][0],points[i - 1][0]);//因为已经按开始坐标排序了，因此这里可以省去
				points[i][1] = Math.min(points[i][1],points[i - 1][1]);
			}else {
				result++;//不能合并，则前面已经合并的区间需要一直箭
			}
		}
		//循环到最后，肯定会剩下一个区间，因为我们算的是不能合并的就给一箭，能合并的就合并然后留着给下一个合并，所以到最后肯定会剩下一个区间
		result ++;
		return result;
    }
}
